{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Written by\n",
    "\n",
    "David Yeo, Ph.D.\n",
    "\n",
    "#### Introduction\n",
    "\n",
    "\n",
    "The knapsack problem, which has been studied for more than a century, is an example of a combinatorial optimization problem. Its popularity is due to its wide-ranging applicability. As Technopedia put it,\n",
    "\n",
    ">The knapsack problem can be found real-world scenarios like resource allocation in financial constraints or even in selecting investments and portfolios. It also can be found in fields such as applied mathematics, complexity theory, cryptography, combinatorics and computer science. It is easily the most important problem in logistics.\n",
    "\n",
    "The following program uses q-learning to generate potential solutions to the knapsack problem. Specifically, it addresses the *unbounded knapsack problem*, which places no upper bound on the number of copies of each kind of item. More formally,\n",
    "\n",
    "$$maximize \\sum \\limits _{i=1} ^{n} w_{i}v_{i}$$\n",
    "\n",
    "$$where \\sum \\limits _{i=1} ^{n} w_{i}x_{i} \\le W,  x_{i} \\ge 0$$\n",
    "\n",
    "Here $x_{i}$ represents the number of instances of item$_i$ to include in the knapsack, and $v_{i}$ and $w_{i}$ are (respectively) the value and the weight of the ith item. $W$ is the maximum weight the knapsack can carry. There are $n$ items that can potentially be packed. \n",
    "\n",
    "**Note:** An implicit constraint is $v_{i}, w_{i} > 0$. It makes no sense to pack items which have no value (i.e. where $v_{i} \\le 0$).  And, although some items (like helium filled balloons) could have a  $w_{i} \\le 0$, if the item has any value at all (i.e. if $v_{i} > 0$), the optimal strategy would be to pack an infinite number of those items. Remember the knapsack's capacity is defined by the total weight, not by volume (which is assumed to be infinite).\n",
    "\n",
    "####  Program Listing\n",
    "\n",
    "Two libraries are required: os and numpy."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-02-01T23:59:35.784339Z",
     "start_time": "2025-02-01T23:59:31.574490Z"
    }
   },
   "outputs": [],
   "source": [
    "import os\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As its name implies, the initialize_memory() function initializes the associative memory to the values stored in the specified long term memory file. If the memory file does not exist, a new associative memory is created and returned."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-02-01T23:59:36.120023Z",
     "start_time": "2025-02-01T23:59:31.996479Z"
    }
   },
   "outputs": [],
   "source": [
    "def initialize_memory(filename):\n",
    "    if os.path.exists(filename): \n",
    "        memory = np.load(filename,allow_pickle='TRUE').item()\n",
    "        return memory \n",
    "    return {}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Read_problem() loads the maximum knapsack capacity (W), the item value vector (v), and item weight (w) vector. These provide the constraints that define the problem to be solved."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-02-01T23:59:40.235038Z",
     "start_time": "2025-02-01T23:59:40.151744Z"
    }
   },
   "outputs": [],
   "source": [
    "def read_problem(filename):\n",
    "    with open(filename) as fp:\n",
    "        W = float(fp.readline())\n",
    "        data = []\n",
    "        for line in fp:\n",
    "            data.append([float(x) for x in line.split()])\n",
    "        v = np.array(data[0])\n",
    "        w = np.array(data[1])\n",
    "    return v,w,W"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Get_possible() returns the list of indices for items that can validly be added to the knapsack. It first determines the amount of weight currently in the knapsack (current_total). It then iterates through each of the available items, checking if the addition of the item's weight would surpass the knapsack's capacity (W)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-02-01T23:59:43.346508Z",
     "start_time": "2025-02-01T23:59:43.286295Z"
    }
   },
   "outputs": [],
   "source": [
    "def get_possible(x,w,W):\n",
    "    n = len(x)\n",
    "    current_total = 0\n",
    "    for i in range(n):\n",
    "        current_total += w[i] * x[i]\n",
    "    possible=[]\n",
    "    for i in range(n): \n",
    "        if current_total + w[i] <= W:\n",
    "            possible.append(i)\n",
    "    return(np.array(possible,dtype=int))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The reinforcement() reward function is responsible for generating the r value in the q-learning equation. For the knapsack problem, this is given by the sum of the number of each item packed (${x_i}$) times the value of the item (${v_i}$)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-02-01T23:59:48.039059Z",
     "start_time": "2025-02-01T23:59:47.963292Z"
    }
   },
   "outputs": [],
   "source": [
    "def reinforcement(x,v):\n",
    "    r = 0.0\n",
    "    for i in range(len(x)):\n",
    "        r += v[i] * x[i]\n",
    "    return r"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Get_q() retrieves the q-value of a specified state-action pair from the associative memory. If either the current state or state-action pair is unknown, get_q() initializes the q-value to a small uniform random value, and then stores it in the associative memory.\n",
    "\n",
    "**Note:** According to reinforcement theory, any initial value works. The disadvantange of assigning a constant is that, when presented with a vector of constants (as occurs when training begins), the numpy.max() function favors the first occurrence. Since each q-value corresponds to an action, this means that the first action is preferentially selected. Initializing the q-values to small random values eliminates this bias."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-02-02T00:00:02.035703Z",
     "start_time": "2025-02-02T00:00:01.952409Z"
    }
   },
   "outputs": [],
   "source": [
    "def get_q(state,action):\n",
    "    initial_value = np.random.uniform(high=0.1)\n",
    "    actions = memory.get(str(state))\n",
    "    if actions == None:\n",
    "        memory[str(state)] = {str(action):initial_value}\n",
    "        return initial_value\n",
    "    q = actions.get(str(action))\n",
    "    if q == None:\n",
    "        memory[str(state)][str(action)] = initial_value\n",
    "        return initial_value\n",
    "    return q"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Get_maxq() returns the maximum q-value for all of the actions that the puzzle has ever encountered. It takes advantage of the nested dictionary memory structure. The function begins by recalling all actions associated with the current state. If the state is unknown, a small uniform random value is returned. Otherwise the values() function recalls the q-values from all of the state's possible actions, and numpy.max() returns the largest."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-02-02T00:00:09.025375Z",
     "start_time": "2025-02-02T00:00:08.944582Z"
    }
   },
   "outputs": [],
   "source": [
    "def get_maxq(state):\n",
    "    initial_value = np.random.uniform(high=0.1)\n",
    "    actions = memory.get(str(state))\n",
    "    if actions == None:\n",
    "        return initial_value \n",
    "    values = list(actions.values())\n",
    "    return np.max(values)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "E_greedy() returns either a randomly selected action (exploration) or the action yielding the maximum q-value (exploitation). The specified epsilon value tells the e_greedy() function  how often, on average, to explore. The default is to explore 10% of the time. Setting epsilon = 0 forces e_greedy() to be greedy. \n",
    "\n",
    "The e_greedy() procedure starts by using the get_possible() procedure to generate a list of the items that can be added without violating the capacity limit. It then converts the possible values into a list of possible actions. If no action is possible, e_greedy() returns the value None. Otherwise, a small uniform random number is generated. If the random value is less than the epsilon parameter, one of the possible actions is randomly selected. Otherwise, the q-values of all of the current puzzle's possible actions are recalled from the associative memory, and the maximum of the q-values is returned."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-02-02T00:00:22.376970Z",
     "start_time": "2025-02-02T00:00:22.296688Z"
    }
   },
   "outputs": [],
   "source": [
    "def e_greedy(state,w,W,epsilon=0.1):\n",
    "    actions = get_possible(state,w,W)\n",
    "    nactions = len(actions)\n",
    "    if nactions == 0:\n",
    "        return None\n",
    "    if np.random.uniform() < epsilon:\n",
    "        action = actions[np.random.randint(0,nactions)]\n",
    "    else:\n",
    "        q_values = []\n",
    "        for i in range(nactions):\n",
    "            q_values.append(get_q(state,actions[i]))\n",
    "        action = actions[np.argmax(q_values)]\n",
    "    return action"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The next procedure, apply_action(), applies the given action to a copy of the incoming state. The action is to add a specified amount (by default=1.0) to the item count in the state (i.e. x vector) identified by the action argument. In principle, any value can be used as the addend; it need not be a whole number. \n",
    "\n",
    "**Note:** This opens up the possibility of designing a function that changes the addend as the situation changes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-02-02T00:00:25.354008Z",
     "start_time": "2025-02-02T00:00:25.279245Z"
    }
   },
   "outputs": [],
   "source": [
    "def apply_action(state,action,addend=1.0):\n",
    "    successor = state.copy()\n",
    "    successor[action] += addend\n",
    "    return successor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The pack() function is another very important algorithm. It (greedily) packs the knapsack based on the action q-values recalled from memory. First, the current state (${s_1}$) of the knapsack is initialized to empty. Then an infinite loop begins. Because the epsilon parameter is set to zero, the greedy variant of e_greedy() is run. This recalls the action with the largest q-value. If no action is found, the infinite loop is broken and the current state (${s_1}$) is returned. Otherwise, the greedy action is applied to the current state, generating its successor (${s_2}$). The successor then becomes the current state in the next iteration."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-02-02T00:00:35.229522Z",
     "start_time": "2025-02-02T00:00:35.163788Z"
    }
   },
   "outputs": [],
   "source": [
    "def pack(w,W):\n",
    "    s1 = np.zeros((len(w)))\n",
    "    while True:\n",
    "        action = e_greedy(s1,w,W,0)     # greedy solution (epsilon=0)\n",
    "        if action == None:\n",
    "            break\n",
    "        print(\"add item\",action+1,\"to knapsack\")\n",
    "        s2 = apply_action(s1,action)\n",
    "        s1 = s2\n",
    "    return s1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The procedure responsible for devising advanced strategies is q_learn(). It is responsible for implementing the q-learning equation. \n",
    "\n",
    "Q_learn() begins by checking if the number of requested trials is > 0. If so, learning begins. First q_learn() determines the number of items to consider. It then executes the requested number of learning trials. At the beginning of each epoch the knapsack is emptied. It is refilled by entering into an infinite loop that can only be broken when e_greedy() determines that no action applies, i.e. the knapsack capacity has been reached. Otherwise, the current state's successor is generated by applying the e_greedy() selected action (${a_1}$) to the current state. This is the last component required to implement the q-learning equation:\n",
    "\n",
    "$${q_1} = {q_1} + \\alpha * (r + \\gamma * {q_2} - c).$$\n",
    "\n",
    "Get_q() recalls the current state's q-value (${q_1}$). Get_maxq() determines ${q_2}$, the largest q-value across all of the actions associated with the successor. And the reinforcement() function is tasked with estimating the successor's reward value (${r}$). The q-learning equation can now be applied. The updated ${q_1}$ value memorized, and the successor state becomes the current state on the next iteration of the infinite loop. \n",
    "\n",
    "Once training is complete, q_learn() calls the pack() procedure. Pack() greedily packs the knapsack and returns it as the proposed solution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-02-02T00:00:48.722938Z",
     "start_time": "2025-02-02T00:00:48.614544Z"
    }
   },
   "outputs": [],
   "source": [
    "def q_learn(v,w,W,ntrials):\n",
    "    if ntrials > 0:\n",
    "        n = len(v)\n",
    "        for t in range(ntrials):\n",
    "            print(\"trial number: \"+str(t+1), end=\"\\r\")\n",
    "            s1 = np.zeros((n))  # empty knapsack\n",
    "            while(True):\n",
    "                a1 = e_greedy(s1,w,W)\n",
    "                if a1 == None:\n",
    "                    break\n",
    "                s2 = apply_action(s1,a1)            \n",
    "                r = reinforcement(s2,v)\n",
    "                q1 = get_q(s1,a1)\n",
    "                q2 = get_maxq(s2)\n",
    "                q1 = q1 + alpha * (r + gamma * q2 - q1)\n",
    "                memory[str(s1)][str(a1)] = q1\n",
    "                s1 = s2\n",
    "        print(\"trial number: \"+str(t+1))\n",
    "    print(\"\\nProposed Solution\\n\")\n",
    "    x = pack(w,W)\n",
    "    return x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The print dictionary() function displays the contents of the long term memory."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-02-02T00:00:50.643805Z",
     "start_time": "2025-02-02T00:00:50.556979Z"
    }
   },
   "outputs": [],
   "source": [
    "def print_dictionary(memory):\n",
    "    for key,value in memory.items():\n",
    "        if isinstance(value,dict):\n",
    "            items = dict(sorted(value.items()))\n",
    "            actions = list(items.keys())\n",
    "            q_values = list(items.values())\n",
    "            best = np.argmax(q_values)\n",
    "            print(\"\\nx:\",key)\n",
    "            print(\"\\nrecommended action:\",actions[best],\"\\n\")\n",
    "            print_dictionary(items)\n",
    "        else:\n",
    "            print(\"action:\",key,\"\\tq-value:\",value)\n",
    "    return"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The main() procedure begins by setting the initial parameter values (e.g. learning rate). It then executes numpy's seed function. The seed function was only used to enable reproducibility of the pseudo-random results. It can be removed. Next the problem and memory files are identified. The associative memory is then recalled from the specified memory file. If the file does not exist, a new (tabula rasa) associative memory is created. \n",
    "\n",
    "**Note:** If the specified problem description file does not exist, Knapsack-Q simply exits.  \n",
    "\n",
    "The problem to be solved is then passed to q_learn(), which generates and displays its potential solution. This is follows by a dump of the memory used to generate the proposed solution. Finally, the long term memory file is updated."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-02-02T00:21:32.157053Z",
     "start_time": "2025-02-02T00:21:32.119415Z"
    }
   },
   "outputs": [],
   "source": [
    "def main():\n",
    "\n",
    "    global alpha                # learning rate (0:1]   \n",
    "    global gamma                # discount factor (0:1] \n",
    "    global memory               # associative memory\n",
    "\n",
    "    alpha = 0.25\n",
    "    gamma = 0.95\n",
    "    \n",
    "    np.random.seed(19521212)    # can be removed\n",
    "    \n",
    "    data_file = \"test.txt\"\n",
    "    memory_file = \"test_ltm.npy\" \n",
    "\n",
    "    if os.path.exists(data_file):\n",
    "        v, w, W = read_problem(data_file)\n",
    "        print(\"Input Data\\n\\nv:\",v,\"\\nw:\",w,\"\\n\\nW:\",W,\"\\n\")\n",
    "        memory = initialize_memory(memory_file)\n",
    "        ntrials = int(input(\"trials requested: \"))\n",
    "        x = q_learn(v,w,W,ntrials)\n",
    "        r = reinforcement(x,v)\n",
    "        print(\"\\nx:\",x,\"\\tr:\",r,\"\\n\\nMemory Contents\")\n",
    "        print_dictionary(memory)\n",
    "        np.save(memory_file,memory)\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    main()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Results\n",
    "\n",
    "The problem illustrated was originally from the Wikipedia entry on the knapsack problem. The specified maximum capacity of the knapsack (W) is 67, and the value ($v_{i}$) and weight ($w_{i}$) of each item are:\n",
    "\n",
    "* **v** = [505. 352. 458. 220. 354. 414. 498. 545. 473. 543.] \n",
    "* **w** = [23. 26. 20. 18. 32. 27. 29. 26. 30. 27.] \n",
    "\n",
    "After 1200 trials, the proposed solution (x) is [2. 0. 1. 0. 0. 0. 0. 0. 0. 0.]. First item 1 is added to the knapsack. Then another item 1 is packed. Finally, item 3 is added. This reaches the weight limit, i.e. 23 + 23 + 20 = 66. A brief history of the changing packing options as learning progresses is presented below.\n",
    "\n",
    "     # Trials           Proposed Solution (x)          Total Value               \n",
    "\n",
    "            0       [0. 0. 2. 0. 0. 0. 0. 0. 0. 1.]       1459.0       \n",
    "            1       [0. 0. 0. 0. 0. 1. 0. 0. 1. 0.]        887.0\n",
    "           10       [0. 0. 0. 0. 0. 1. 0. 0. 1. 0.]        887.0\n",
    "          100       [0. 0. 0. 0. 0. 1. 0. 0. 1. 0.] \t   887.0 \n",
    "         1000       [0. 0. 0. 2. 0. 0. 0. 0. 1. 0.] \t   913.0\n",
    "         1050       [0. 0. 0. 2. 0. 0. 0. 0. 1. 0.] \t   913.0\n",
    "         1100       [0. 0. 0. 2. 0. 0. 0. 0. 1. 0.] \t   913.0\n",
    "         1150       [0. 0. 0. 2. 0. 0. 0. 0. 1. 0.] \t   913.0\n",
    "         1200       [2. 0. 1. 0. 0. 0. 0. 0. 0. 0.] \t  1468.0\n",
    "         1250       [2. 0. 1. 0. 0. 0. 0. 0. 0. 0.] \t  1468.0\n",
    "         1500       [2. 0. 1. 0. 0. 0. 0. 0. 0. 0.]       1468.0\n",
    "         5000       [2. 0. 1. 0. 0. 0. 0. 0. 0. 0.] \t  1468.0\n",
    "        10000       [2. 0. 1. 0. 0. 0. 0. 0. 0. 0.] \t  1468.0\n",
    "        25000       [2. 0. 1. 0. 0. 0. 0. 0. 0. 0.] \t  1468.0\n",
    "\n",
    "The maximum value of the packed knapsack seems to have stablized at 1468. Of course, it is possible that further training could discover an even more profitable solution. \n",
    "\n",
    "#### Discussion\n",
    "     \n",
    "Several revealing two item tests of the algorithm were run. These early explorations of the Knapsack-Q algorithm's ability are presented below. To increase the chance of convergence, in each of the following problems 25000 learning trials were requested. \n",
    "\n",
    "First, consider the case in which the more valueable item weighs less. There are two variants of this problem (see below). In both cases the Knapsack-Q algorithm found the optimal solution, i.e. select as many of the light weight, more valuable, items as possible.\n",
    "\n",
    "    ----- Input Data -----            Proposed Solution       Value\n",
    "      \n",
    "    v=[1 2]  w=[2 1]  W=10                 [ 0. 10.] \t      20.0\n",
    "    v=[2 1]  w=[1 2]  W=10                 [10.  0.] \t      20.0\n",
    "\n",
    "Next consider the case were the weights are the same, but the values are different. The cases are itemized below. The optimal solution is clear; since all items weigh the same, pack as many of the most valuable items as possible. Again Knapsack-Q generated the optimal solution. \n",
    "\n",
    "    ----- Input Data -----            Proposed Solution       Value\n",
    "    \n",
    "    v=[1 2]  w=[1 1]  W=10                 [ 0. 10.] \t      20.0       \n",
    "    v=[2 1]  w=[1 1]  W=10                 [10.  0.] \t      20.0              \n",
    "\n",
    "Another interesting test is assigning the same value to both items. The two variants of this test are shown below. In both cases the optimal solution was discovered, i.e. take as many of the lighter weight items as possible.\n",
    "\n",
    "    ----- Input Data -----            Proposed Solution       Value\n",
    "    \n",
    "    v=[1 1]  w=[1 2]  W=10                 [10.  0.] \t      10.0        \n",
    "    v=[1 1]  w=[2 1]  W=10                 [ 0. 10.] \t      10.0\n",
    "\n",
    "Finally, it is important to remember that neither the total capacity of the knapsack nor the value and the weight vectors need be whole numbers. The following problems illustrate this.\n",
    "\n",
    "    ---------- Input Data ---------   Proposed Solution      Value\n",
    "    \n",
    "    v=[1.1 1.2]  w=[1.1 1.2]  W=10.5       [3. 6.]           10.5\n",
    "    v=[1.2 1.1]  w=[1.1 1.2]  W=10.5       [9. 0.]           10.799999999999999\n",
    "    v=[1.1 1.2]  w=[1.1 1.4]  W=10.5       [7. 2.]           10.100000000000001\n",
    "    v=[1.1 1.2]  w=[1.3 1.4]  W=10.5       [0. 7.]            8.4    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
